<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN" "http://www.w3.org/TR/html4/loose.dtd">
<html>
<head>
<title>/media/src/Dropbox/TC/SingleRoundMatch/TCCC2003/TCCC2003Round02/TCCC2003Round02Div1_500.h.html</title>
<meta name="Generator" content="Vim/7.2">
<meta http-equiv="content-type" content="text/html; charset=UTF-8">
</head>
<body bgcolor="#ffffff" text="#000000"><font face="monospace">
<font color="#8080ff">//Fri Jun 10 01:27:14 CDT 2011</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;vector&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;list&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;map&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;set&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;deque&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;stack&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;bitset&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;algorithm&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;functional&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;numeric&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;utility&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;sstream&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;iostream&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;iomanip&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cstdio&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cstring&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cmath&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;cstdlib&gt;</font><br>
<font color="#ff40ff">#include </font><font color="#ff6060">&lt;ctime&gt;</font><br>
<br>
<font color="#ffff00">using</font>&nbsp;<font color="#00ff00">namespace</font>&nbsp;std;<br>
<br>
<font color="#00ff00">class</font>&nbsp;Marketing {<br>
<font color="#ffff00">public</font>:<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">long</font>&nbsp;<font color="#00ff00">long</font>&nbsp;howMany(vector &lt;string&gt;);<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">bool</font>&nbsp;dfs(<font color="#00ff00">int</font>&nbsp;x, <font color="#00ff00">int</font>);<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">bool</font>&nbsp;grid[<font color="#ff6060">31</font>][<font color="#ff6060">31</font>];<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;type[<font color="#ff6060">31</font>];<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;N;<br>
};<br>
<br>
<font color="#00ff00">bool</font>&nbsp;Marketing::dfs(<font color="#00ff00">int</font>&nbsp;x, <font color="#00ff00">int</font>&nbsp;b){<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(type[x] &gt;= <font color="#ff6060">0</font>) <font color="#ffff00">return</font>&nbsp;type[x] == b;<br>
&nbsp;&nbsp;&nbsp;&nbsp;type[x] = b;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;i=<font color="#ff6060">0</font>; i&lt;N; i++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(grid[x][i] &amp;&amp; dfs(i, <font color="#ff6060">1</font>-b)==<font color="#ff6060">false</font>)<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;<font color="#ff6060">false</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;<font color="#ff6060">true</font>;<br>
}<br>
<br>
<font color="#00ff00">long</font>&nbsp;<font color="#00ff00">long</font>&nbsp;Marketing::howMany(vector &lt;string&gt; compete) {<br>
&nbsp;&nbsp;&nbsp;&nbsp;memset(grid, <font color="#ff6060">false</font>, <font color="#ffff00">sizeof</font>(grid));<br>
&nbsp;&nbsp;&nbsp;&nbsp;memset(type, -<font color="#ff6060">1</font>, <font color="#ffff00">sizeof</font>(type));<br>
&nbsp;&nbsp;&nbsp;&nbsp;N = compete.size();<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;i=<font color="#ff6060">0</font>; i&lt;N; i++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stringstream s(compete[i]);<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">int</font>&nbsp;num;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">while</font>(s &gt;&gt; num){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;grid[i][num] = <font color="#ff6060">true</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;grid[num][i] = <font color="#ff6060">true</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#00ff00">long</font>&nbsp;<font color="#00ff00">long</font>&nbsp;ret = <font color="#ff6060">1LL</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">for</font>(<font color="#00ff00">int</font>&nbsp;i=<font color="#ff6060">0</font>; i&lt;N; i++){<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(type[i] &lt; <font color="#ff6060">0</font>){<br>
<font color="#8080ff">//&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;type[i] = 0;</font><br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;ret &lt;&lt;= <font color="#ff6060">1</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">if</font>(dfs(i, <font color="#ff6060">0</font>)==<font color="#ff6060">false</font>) <font color="#ffff00">return</font>&nbsp;-<font color="#ff6060">1</font>;<br>
&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;}<br>
&nbsp;&nbsp;&nbsp;&nbsp;<font color="#ffff00">return</font>&nbsp;ret;<br>
}<br>
<br>
<font color="#8080ff">//&lt;%:testing-code%&gt;</font><br>
<font color="#8080ff">//Powered by [KawigiEdit] 2.0!</font><br>
</font></body>
</html>
